\chapter{Лекция 6. Контекстно-свободные грамматики и языки}

\section{Напоминание}

\begin{Def}
Контекстно-свободный язык - язык, который описывается контекстно-свободной грмматикой.
\end{Def}

\begin{Def}
Контекстно-свободная грамматика - грамматика, в которой в левой части правила всегда стоит нетерминал, а правой части произвольная непустая цепочка
из терминалов и нетерминалов.
\end{Def}

\section{Удаление цепных правил}

TODO: дописать

\section{Нормальная форма Хомского}

Грамматика, правила которой имеют вид:
\[
	\begin{split}
		&A ::= a\\
		&A ::= BC
	\end{split}
\]
где заглавные символы - нетерминалы, а малые - терминалы.

После устранения цепных правил, все правила, в которых в правой части всего один символ, имеют первую форму. Осталось все правила с несколькими символами
в правой части преобразовать к нужному виду, для этого разбиваем правую часть на голову и хвост, где голова первый символ правой части правила, а хвост
все оставшиеся. Если правило имело вид $A ::= h TAIL$, то заменяем его на правила $A ::= H TAIL$ и $H ::= h$, если правило имело вид $A ::= H TAIL$ и если
$TAIL$ - цепочка, а не один нетерминал, тогда заменяем это правило на пару правил $A ::= H T$ и $T ::= TAIL$. Данная процедура повторяется, пока есть правила
неудовлетворяющие нормальной форме Хомского.

Выше приведен алгоритм последовательного преобразования грамматики к нормальной форме Хомского, т. е. произвольная КС грамматика может быть приведена к нормальной
форме Хомского.

\begin{Def}
Размер грамматики - сумма длинн всех правил.
\end{Def}

\paragraph{Нормализация по Хомскому грамматики без цепных правил увеличивает ее размер квадратично}

\paragraph{Устранение цепных правил увеличивает ее размер линейно.}

\paragraph{Давайте сначала пробовать нормализовать, а затем устранять цепные правила.}

\section{Алгоритм Кока-Янгера-Касами}

Пусть имеется некоторое слово, как проверить, что оно принадлежит языку? Нужно проверить, что оно выводится из стартового нетерминала. Пусть имеется правило
вывода $S :: = \alpha$, где $\alpha$ - строка из терминалов и нетерминалов. Нужно просмотреть все возможные разбиения слова на $|\alpha|$ подслов, так чтобы
подслова соответствующие терминалам были равными терминалами, а нетерминалам соответсвовали произвольные подслова. Рекурсивно повторяем процесс для подслов
соответсвующих нетерминалам, если такого разбиения нет то проверяемое подслово не выводимо из заданного нетерминала.

Если грамматика задана в нормальной форме Хомского, то достаточно тяжелая процедура разбиения и перебора может быть упращена и преобразована в простой
алгоритм. Пусть мы проверяем слово $w$, заведем таблицу $T = |w|\times|w|$, элемент в позиции $T_{i,j}$ содержаться все нетерминалы, из которых выводимо
подслово $w[i:j]$.

Процедура заполнения $T$ очень проста, на диагонали расставляем все элементы слова $w$, добавляем к диагональным элементам соответсвующим терминалам все
нетерминалы (в строке только терминалы, не забываем), в правой части которых он располагается, т. е. все такие $N_i$, что правило $N_i ::= a_i$, где
$a_i$ - указанный терминал.

Далее пусть на $n$-ом шаге заполнение имеем подслово $u$, перебираем все его разбиения на 2 непустых подслова $u_l$ и $u_r$, рассмотрим все нетерминалы
из которых выводимы $u_l$ и $u_r$ комбинруем их в пары и проверяем сущестование такого правила в грамматике, если такое правило существует, то добавляем
его левую часть в ячейку соответсвующую $u$.

В конце работы алгоритма проверяем, что в ячейке $T(1,|w|)$ содержится стартовый нетерминал.

\section{Лемма о разрастании для КС языков}

Пусть $G$ - КС грамматика в нормальной форме Хомского. Пусть $w$ - слово принадлежащее $L(G)$. Пусть $T$ - дерево вывода слова $w$. Если $h$ - высота дерева
$T$, тогда $|w| \le 2^{h-1}$ - это понятно, так как грамматика в нормальной фоме Хосмкого. Пусть в грамматике есть $n$ нетерминалов, тогда в дереве вывода
любой цепочки длинны $> 2^n$ существует путь от корня к листу, в котором нетерминалы повторяются (ну это очевидно, так как высота дерева больше $n$). Пусть
повторяющийся нетерминал $A$, обозначим его повторные вхождения как $A_1$ и $A_2$, и $A_2$ ниже $A_1$ в дереве вывода.

Пусть из $A_2$ выведена терминальная подцепочка $z$. А из $A_1$ выведена подцепочка $uzv$, причем $u$ и $v$ не могут быть одновременно пустыми, то есть
$w = x uzv y$, где $|ux| \ge 1$ и $|uzv| \le 2^n$.

\begin{Lem}[о разрастании]
Пусть $L$ - КС язык, тогда $\exists n \in \mathbb{N}$, что для любой цепоки $w \in L$ такой что $|w| > n$ существует представление:
$w = xuzvy$, такое что $|uzv| \le n$, $|uv| \ge 1$ и $xu^izv^iy \in L$ снова.
\end{Lem}

\begin{Proof}
Из проведенных выше рассуждений видно, что если и $z$ и $uzv$ выводимы из одного нетерминала $A$, то существует вывод цепочки $A \Rightarrow^{*} uAv$, а
тогда очевидно, что $A \Rightarrow^{*} u^iAv^i \Rightarrow^{*} u^izv^i$
\end{Proof}

\paragraph{Пример}

Рассмотрим язык $L = \{a^pb^pc^p | p \ge 1\}$, докажем, что он не КС. Пусть он КС, тогда существует такой $n$, что для любой цепочки $|w| > n$ выполнены
все следствия леммы о накачке. Возьмем цепочку которая начинается с $a^{p>n}$, вся цепочка имеет длинну $3p > 3n$, и значит как бы мы не выбирали $u$, $z$ и
$v$ в $uzv$ не может быть больше 2 различных символов, а значит если мы начнем повторять многократно $u$ и $v$, то мы получаем цепочку не принадлежащую языку.

\section{Лемма Огдена}

\begin{Def}
Дерево является помеченным, если в каждом его поддереве имеется помеченный лист
\end{Def}

Если помеченная высота дерева $h$ (высота максимального помеченного поддерева), тогда количество помеченных листов $\le 2^h$.

\section{Бесконечность КС-языков}

Используя лемму о накачке легко понять, что если в языке существует слово длинны $>n$, то язык бесконечен, как определить, что такое слово существует? Достаточно
на самом деле проверять слова длинны от $n$ до $2n$, если таких слов нет, то и слов большей длинны не будет. На самом деле суть в том, что любое достаточно длинное
слово уже накачано, то есть мы его можем сдуть взяв в лемме параметр $i = 0$ мы сдуем слово.
